// Copyright (c) 2005-2008, Simon Howard
// Permission to use, copy, modify, and/or distribute this software
// for any purpose with or without fee is hereby granted, provided
// that the above copyright notice and this permission notice appear
// in all copies.
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
// WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
// WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE
// AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR
// CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
// NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

use std::collections::VecDeque;

/// A generic queue implementation using `VecDeque`.
pub struct Queue<T> {
    inner: VecDeque<T>,
}

impl<T> Queue<T> {
    /// Creates a new empty queue.
    pub fn new() -> Self {
        Queue {
            inner: VecDeque::new(),
        }
    }

    /// Pushes an element to the head of the queue.
    pub fn push_head(&mut self, value: T) {
        self.inner.push_front(value);
    }

    /// Pushes an element to the tail of the queue.
    pub fn push_tail(&mut self, value: T) {
        self.inner.push_back(value);
    }

    /// Pops an element from the head of the queue.
    /// Returns `None` if the queue is empty.
    pub fn pop_head(&mut self) -> Option<T> {
        self.inner.pop_front()
    }

    /// Pops an element from the tail of the queue.
    /// Returns `None` if the queue is empty.
    pub fn pop_tail(&mut self) -> Option<T> {
        self.inner.pop_back()
    }

    /// Peeks at the element at the head of the queue without removing it.
    /// Returns `None` if the queue is empty.
    pub fn peek_head(&self) -> Option<&T> {
        self.inner.front()
    }

    /// Peeks at the element at the tail of the queue without removing it.
    /// Returns `None` if the queue is empty.
    pub fn peek_tail(&self) -> Option<&T> {
        self.inner.back()
    }

    /// Checks if the queue is empty.
    pub fn is_empty(&self) -> bool {
        self.inner.is_empty()
    }
}

// Test cases for the queue

#[cfg(test)]
mod tests {
    use super::Queue;

    #[test]
    fn test_queue_new_free() {
        let mut queue: Queue<i32> = Queue::new();

        // Create and destroy a queue
        assert!(queue.is_empty());

        // Add lots of values and then destroy
        for _ in 0..1000 {
            queue.push_head(1);
        }
        assert!(!queue.is_empty());
    }

    #[test]
    fn test_queue_push_head() {
        let mut queue: Queue<i32> = Queue::new();

        // Add some values
        for _ in 0..1000 {
            queue.push_head(1);
            queue.push_head(2);
            queue.push_head(3);
            queue.push_head(4);
        }

        assert!(!queue.is_empty());

        // Check values come out of the tail properly
        assert_eq!(queue.pop_tail(), Some(1));
        assert_eq!(queue.pop_tail(), Some(2));
        assert_eq!(queue.pop_tail(), Some(3));
        assert_eq!(queue.pop_tail(), Some(4));

        // Check values come back out of the head properly
        assert_eq!(queue.pop_head(), Some(4));
        assert_eq!(queue.pop_head(), Some(3));
        assert_eq!(queue.pop_head(), Some(2));
        assert_eq!(queue.pop_head(), Some(1));
    }

    #[test]
    fn test_queue_pop_head() {
        let mut queue: Queue<i32> = Queue::new();

        // Check popping off an empty queue
        assert_eq!(queue.pop_head(), None);

        // Pop off all the values from the queue
        let mut queue = generate_queue();

        while !queue.is_empty() {
            assert_eq!(queue.pop_head(), Some(4));
            assert_eq!(queue.pop_head(), Some(3));
            assert_eq!(queue.pop_head(), Some(2));
            assert_eq!(queue.pop_head(), Some(1));
        }

        assert_eq!(queue.pop_head(), None);
    }

    #[test]
    fn test_queue_peek_head() {
        let mut queue: Queue<i32> = Queue::new();

        // Check peeking into an empty queue
        assert_eq!(queue.peek_head(), None);

        // Pop off all the values from the queue, making sure that peek
        // has the correct value beforehand
        let mut queue = generate_queue();

        while !queue.is_empty() {
            assert_eq!(queue.peek_head(), Some(&4));
            assert_eq!(queue.pop_head(), Some(4));
            assert_eq!(queue.peek_head(), Some(&3));
            assert_eq!(queue.pop_head(), Some(3));
            assert_eq!(queue.peek_head(), Some(&2));
            assert_eq!(queue.pop_head(), Some(2));
            assert_eq!(queue.peek_head(), Some(&1));
            assert_eq!(queue.pop_head(), Some(1));
        }

        assert_eq!(queue.peek_head(), None);
    }

    #[test]
    fn test_queue_push_tail() {
        let mut queue: Queue<i32> = Queue::new();

        // Add some values
        for _ in 0..1000 {
            queue.push_tail(1);
            queue.push_tail(2);
            queue.push_tail(3);
            queue.push_tail(4);
        }

        assert!(!queue.is_empty());

        // Check values come out of the head properly
        assert_eq!(queue.pop_head(), Some(1));
        assert_eq!(queue.pop_head(), Some(2));
        assert_eq!(queue.pop_head(), Some(3));
        assert_eq!(queue.pop_head(), Some(4));

        // Check values come back out of the tail properly
        assert_eq!(queue.pop_tail(), Some(4));
        assert_eq!(queue.pop_tail(), Some(3));
        assert_eq!(queue.pop_tail(), Some(2));
        assert_eq!(queue.pop_tail(), Some(1));
    }

    #[test]
    fn test_queue_pop_tail() {
        let mut queue: Queue<i32> = Queue::new();

        // Check popping off an empty queue
        assert_eq!(queue.pop_tail(), None);

        // Pop off all the values from the queue
        let mut queue = generate_queue();

        while !queue.is_empty() {
            assert_eq!(queue.pop_tail(), Some(1));
            assert_eq!(queue.pop_tail(), Some(2));
            assert_eq!(queue.pop_tail(), Some(3));
            assert_eq!(queue.pop_tail(), Some(4));
        }

        assert_eq!(queue.pop_tail(), None);
    }

    #[test]
    fn test_queue_peek_tail() {
        let mut queue: Queue<i32> = Queue::new();

        // Check peeking into an empty queue
        assert_eq!(queue.peek_tail(), None);

        // Pop off all the values from the queue, making sure that peek
        // has the correct value beforehand
        let mut queue = generate_queue();

        while !queue.is_empty() {
            assert_eq!(queue.peek_tail(), Some(&1));
            assert_eq!(queue.pop_tail(), Some(1));
            assert_eq!(queue.peek_tail(), Some(&2));
            assert_eq!(queue.pop_tail(), Some(2));
            assert_eq!(queue.peek_tail(), Some(&3));
            assert_eq!(queue.pop_tail(), Some(3));
            assert_eq!(queue.peek_tail(), Some(&4));
            assert_eq!(queue.pop_tail(), Some(4));
        }

        assert_eq!(queue.peek_tail(), None);
    }

    #[test]
    fn test_queue_is_empty() {
        let mut queue: Queue<i32> = Queue::new();

        assert!(queue.is_empty());

        queue.push_head(1);
        assert!(!queue.is_empty());

        queue.pop_head();
        assert!(queue.is_empty());

        queue.push_tail(1);
        assert!(!queue.is_empty());

        queue.pop_tail();
        assert!(queue.is_empty());
    }

    /// Helper function to generate a queue with some values.
    fn generate_queue() -> Queue<i32> {
        let mut queue: Queue<i32> = Queue::new();
        for _ in 0..1000 {
            queue.push_head(1);
            queue.push_head(2);
            queue.push_head(3);
            queue.push_head(4);
        }
        queue
    }
}
